#include<stdlib.h>
#include <stdio.h>
#include "LinkedList.h"

LinkedList *createNode(ElemType e) {
    LinkedList *newNode = malloc(sizeof *newNode);
    newNode->data = e;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 初始化双向链表
LinkedList *initLinkedList() {
    // 初始化头尾指针
    LinkedList *head = createNode(' ');
    return head;
}

int verificationLinkedList(LinkedList *linkedList) {
    return linkedList == NULL ? 0 : 1;
}


// 添加元素
int addLinkedList(LinkedList *linkedList, ElemType e) {
    if (!verificationLinkedList(linkedList)) {
        return 0;
    }

    LinkedList *p = linkedList;
    while (p->next != NULL) {
        p = p->next;
    }
    LinkedList *newNode = createNode(e);
    newNode->prev = p;
    p->next = newNode;
    return 1;
}

// 添加链表
int addAllLinkedList(LinkedList *linkedList, LinkedList *ll) {
    if (!verificationLinkedList(linkedList) || !verificationLinkedList(ll)) {
        return 0;
    }
    LinkedList *p = linkedList;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = ll->next;
    ll->next->prev = p;
    return 1;
}

// 删除第i个节点数据
int deleteIndexLinkedList(LinkedList *linkedList, int index) {
    if (!verificationLinkedList(linkedList)) {
        return 0;
    }
    LinkedList *p = getLinkedListByIndex(linkedList, index);
    if (p == NULL) {
        return 0;
    }
    if (p->next == NULL) {
        // p是当前需要删除的元素,并且最后一个元素
        p->prev->next = NULL;
        free(p);
    } else {
        p->prev->next = p->next;
        p->next->prev = p->prev;
        free(p);
    }
    return 1;
}

// 输出双向链表
void showLinkedList(LinkedList *linkedList) {
    if (!verificationLinkedList(linkedList)) {
        return;
    }
    printf("[");
    int n = 0;
    LinkedList *p = linkedList;
    while (p->next != NULL) {
        p = p->next;
        printf("'%c',", p->data);
        n++;
    }
    printf("]==> 长度 %d\n", n);
}

// 双向链表长度
int linkedListLength(LinkedList *linkedList) {
    if (!verificationLinkedList(linkedList)) {
        return 0;
    }
    LinkedList *p = linkedList;
    int size = 0;
    while (p->next != NULL) {
        p = p->next;
        size++;
    }
    return size;
}

// 判断双向链表是否为空
int isEmptyLinkedList(LinkedList *linkedList) {
    return !verificationLinkedList(linkedList) || linkedList->next == NULL;
}

// 输出双向链表给定位置的元素
ElemType getElemTypeLinkedList(LinkedList *linkedList, int index) {
    if (!verificationLinkedList(linkedList)) {
        return ' ';
    }
    LinkedList *p = linkedList;
    int i = 0;
    while (p->next != NULL) {
        p = p->next;
        if (i == index) {
            return p->data;
        }
        i++;
    }
    return ' ';
}

LinkedList *getLinkedListByIndex(LinkedList *linkedList, int index) {
    if (!verificationLinkedList(linkedList)) {
        return NULL;
    }
    int i = 0;
    LinkedList *p = linkedList;
    while (p->next != NULL && i < index + 1) {
        p = p->next;
        i++;
    }
    if (i == index + 1) {
        return p;
    }
    return NULL;
}

// 查找元素的位置
int getIndexLinkedList(LinkedList *linkedList, ElemType e) {
    if (!verificationLinkedList(linkedList)) {
        return -1;
    }
    LinkedList *p = linkedList;
    for (int i = 0; p->next != NULL; i++) {
        p = p->next;
        if (p->data == e) {
            return i;
        }
    }
    return -1;
}

// 在固定位置插入元素
int addIndexLinkedList(LinkedList *linkedList, int index, ElemType e) {
    if (!verificationLinkedList(linkedList)) {
        return 0;
    }
    int i = 0;
    LinkedList *p = linkedList;
    while (p->next != NULL) {
        p = p->next;
        if (i == index) {
            LinkedList *newNode = createNode(e);
            newNode->prev = p->prev;
            p->prev->next = newNode;
            newNode->next = p;
            p->prev = newNode;
            return 1;
        }
        i++;
    }
    return 0;
}

// 释放内存, 尾部删除
void deleteLinkedList(LinkedList *linkedList) {
    if (linkedList == NULL) {
        return;
    }
    LinkedList *p = linkedList;
    while (p->next != NULL) {
        p = p->next;
    }
    while (p != NULL) {
        LinkedList *node = p;
        p = p->prev;
        free(node);
    }
}

void linkedListTest() {
    LinkedList *head = initLinkedList();
    printf("LinkedList是否为空 %s\n", isEmptyLinkedList(head) == 1 ? "true" : "false");
    printf("LinkedList长度 %d\n", linkedListLength(head));
    addLinkedList(head, 'a');
    addLinkedList(head, 'b');
    addLinkedList(head, 'c');
    addLinkedList(head, 'd');
    addIndexLinkedList(head, 3, 'z');
    showLinkedList(head);

    LinkedList *l = initLinkedList();
    addLinkedList(l, '1');
    addLinkedList(l, '2');
    addLinkedList(l, '3');
    showLinkedList(l);
    addAllLinkedList(head, l);
    showLinkedList(head);
    int i = 3;
    LinkedList *t = getLinkedListByIndex(head, i);
    printf("查找第%d个元素 '%c'\n", i, t == NULL ? ' ' : t->data);
    deleteIndexLinkedList(head, 7);
    showLinkedList(head);
    i = 6;
    printf("输出%d个元素是: %c\n", i, getElemTypeLinkedList(head, i));
    ElemType data = 'd';
    printf("查找'%c'元素的位置是：%d\n", data, getIndexLinkedList(head, data));

    deleteLinkedList(head);
}